package alg

import "fmt"

func InsertSortRun() {
	//定义一个数组
	arr := []int{3, 1, 12, 7, 17, 30, 15, 50, 55, 76, 75}
	InsertSort(arr)
	fmt.Println("main arr=", arr, "len=", len(arr))
}

// 直接插入排序, 每一步将一个待排序的记录, 插入到前面已经排好序的有序序列中去, 直到插完所有元素为止
// 最好的情况, 需要进行 n-1 次, 无需交换元素, 时间复杂度 O(n2), 最坏的情况下时间复杂度 还是 O(n2)
// 插入排序要优于 冒泡和选择排序
func InsertSort(arr []int) {
	arrLen := len(arr)
	// 进行两两比较
	for i := 1; i < arrLen; i++ {
		fmt.Println("每次 i循环 i = ,", i)
		j := i

		// 判断本次元素大于 前一个元素则本次无需处理
		if arr[i] > arr[i-1] {
			continue
		}

		// 本次元素是否小于 i -1 元素 则进行交换, 并减少 j 游标
		for j > 0 && arr[j] < arr[j-1] {
			fmt.Println("每次 j循环 j = ,", j, "left=", arr[j], "right=", arr[j - 1])
			arr[j], arr[j - 1] = arr[j - 1], arr[j]
			j--
		}
	}
}
